#include "AC_DFA.h"
#include <deque>
#include <cstring>
#include <cctype>
#include <iomanip>

using std::cout;
using std::left;
using std::setw;
using std::endl;

//查找str内容,匹配找到的关键字,返回该关键字的下标
char *AC_DFA::Find(const char *raw_content, int &keyword_index)
{
	int State=0;
	const unsigned char *p=reinterpret_cast<unsigned char *>(const_cast<char *>(raw_content));
	while(*p)
	{
		State=Goto[State][*p];
		int index=Goto[State][OUTPUT]-1;
		if(index>=0)
        {
            keyword_index=index;
            return reinterpret_cast<char *>(const_cast<unsigned char *>(p+1));
            //cout<<"Find "<<setw(10)<<Keywords[keyword_index].value<<" in "<<p+1<<endl;

        }

		++p;
	}

    return NULL;
}

char *AC_DFA::Find4Len(const char *raw_content, int &keyword_index, unsigned int len)
{
	int State=0;
    const unsigned char *content=reinterpret_cast<unsigned char *>(const_cast<char *>(raw_content));
	const unsigned char *p=content;
    while(static_cast<unsigned int>(p-content)<len)
	{
		State=Goto[State][*p];
		int index=Goto[State][OUTPUT]-1;

		if(index>=0 )
        {
            keyword_index=index;
            return reinterpret_cast<char *>(const_cast<unsigned char *>(p+1));

        }
		++p;
	}

    return NULL;

}

char *AC_DFA::Find4Exact(const char *raw_content, int &keyword_index, unsigned int len)
{
	int State=0;
    const unsigned char *content=reinterpret_cast<unsigned char *>(const_cast<char *>(raw_content));
	const unsigned char *p=content;
    unsigned int matched_len=0;
    while(matched_len<len)
	{
		State=Goto[State][*p];
		int index=Goto[State][OUTPUT]-1;

		if(index>=0 && Keywords[index].value.size()==len)
        {
            keyword_index=index;
            return reinterpret_cast<char *>(const_cast<unsigned char *>(p+1));
        }

		++p;
        matched_len=p-content;
	}

    return NULL;

}
//构建状态转换图
//
//构建的状态转换图是根据保存到Keywords中的关键字来进行的
//构建完毕的状态数是不会大于
//{所有关键字占用的字节数+1}
void AC_DFA::BuildStep1()
{
	int NowState=0;
	int NextState=0;

	//因为考虑有些关键字会有重复，所以不再直接分配
	//{所有关键字占用的字节数+1}的空间，而是增加一
	//个状态就push_back(tmp)一次来增大状态转换图
	//这里的ASC+1是专门为Output留出的一个位置
	std::vector<int> tmp(ASC+1);

	//增加状态0
	Goto.push_back(tmp);

	//依次对每一个关键字进行处理
	for(unsigned int i=0; i<Keywords.size(); ++i)
	{
		//所有关键字的处理都要从状态0开始
		NowState=0;
		NextState=0;

		for(unsigned int j=0; j<Keywords[i].value.size(); ++j)
		{
			unsigned char ch=Keywords[i].value[j];

		
			//当前状态没有通过ch到下一个状态的路径	
			if(Goto[NowState][ch]==0){

				TotolStates+=1;
				NextState=TotolStates;
				Goto[NowState][ch]=NextState;
				NowState=NextState;
				//增加一个状态
				Goto.push_back(tmp);

			}else{
			//当前状态可以通过c到下一状态

				NowState=Goto[NowState][ch];	
			}		
		}

        //这种情况说明两个关键字是相同的，则需要连接两个关键字
        //然后再把自己的信息替换到OUTPUT中
        if(Goto[NowState][OUTPUT]>0)
        {
            Keywords[i].next=Goto[NowState][OUTPUT]-1;
        }
        //当前状态是第i+1个关键字的Ouput状态
        //这里的计数从1开始
        Goto[NowState][OUTPUT]=i+1;
    }

    //缩减内存
    std::vector<std::vector<int> > shrink(Goto);
    std::swap(Goto,shrink);
}


//利用fail函数修改状态转换图
void AC_DFA::BuildStep2()
{
    std::deque<int> Queue;
    int NowState=0;

    //Fail函数，每一个状态都有一个Fail函数值,
    //+1是加上了状态0的Fail函数
    int Fail[TotolStates+1];

    std::memset(Fail, 0, sizeof(int)*(TotolStates+1) );

    //把状态0看成是树根，收集从状态0出发深度为1的状态
    for(int i=0; i<ASC; ++i)
    {
        if(Goto[0][i]!=0){
            Queue.push_back(Goto[0][i]);
            //相应的Fail函数值设为0,
            //前面的memset已经做了这项工作
        }

    }	

    while(!Queue.empty())
    {
        NowState=Queue.front();

        for(int i=0; i<ASC; ++i)
        {
            if(Goto[NowState][i]!=0)
            {
                //把状态转换图看成一棵树的话，
                //现在保存的是NowState的下一层
                //状态,整个过程类似于按层遍历
                int next_state=Goto[NowState][i];
                Queue.push_back(next_state);
                //计算Fail函数
                int next_fail=Fail[ Goto[NowState][i] ]=Goto[ Fail[NowState] ][i];

                //1.如果next_state的OUTPUT没有到达一个关键字，而失败状态(即fail_state)能到达一个关键字的话，
                //next_state的状态也能到达，设置next_state状态的OUTPUT标志与next_fail的一样,
                //
                //2.如果next_state的OUTPUT已经指向一个最终状态，同时next_fail的OUTPUT也指向一个最终状态，根据fail函数
                //定义，next_fail所指的关键字将是next_state的后缀串，因而把它们通过next指针串起来
                //
                //针对条件1的说明：
                //  设有关键字"bcd","abcdef"，在查找字符串"abcdefghijk"匹配到abcd的时候,当前状态的OUTPUT标识是空的而当前状态的
                //  fail状态却是bcd关键字
                //
                //针对条件2的说明：
                //  设有关键字"f","ef","cdef","abcdef",在查找字符串"123abcdefghijk"的时候，会先找到"abcdef"这个关键字，但是它的失败状态
                //  是"cdef"，而"cdef"的失败状态是"ef"，而"ef"的失败状态是"f"，所以这种情况下，需要把它们给串起来
 
                if(Goto[next_fail][OUTPUT]>0 && Goto[next_state][OUTPUT]==0)
                    Goto[next_state][OUTPUT]=Goto[next_fail][OUTPUT];

                else if(Goto[next_fail][OUTPUT]>0 && Goto[next_state][OUTPUT]>0)
                {
                    //通过next指针把当前Fail状态后的OUTPUT函数串联起来
                    int index=Goto[next_state][OUTPUT]-1;
                    while(Keywords[index].next!=-1)
                    {
                        index=Keywords[index].next;
                    }
                    Keywords[index].next=Goto[next_fail][OUTPUT]-1;
                }


            }else{

                Goto[NowState][i]=Goto[Fail[NowState]][i];
            }

        }

        Queue.pop_front();
    }

}

/*

#ifdef _DEBUG
int main()
{
AC_DFA MyDFA;
MyDFA.AddKeyword("ab",1,9,NULL);
MyDFA.AddKeyword("ttabcd",2,10,NULL);
MyDFA.AddKeyword("xttabcdzz",3,11,NULL);
MyDFA.AddKeyword("cdzz",4,12,&MyDFA);
MyDFA.BuildAll();
std::string Content("xttabcdzzakk");
int which=-1;
char *content=MyDFA.Find(Content,which);
std::cout<<MyDFA.GetKeywords(which)<<" "<<content<<std::endl;
MyDFA.ShowKeywords();
}
#endif
 */
